package graph;

import java.util.Arrays;

/**
 * O(v*e) Bipartite hungary solution
 * 
 * @author yinzichen
 * 
 */
public class Hungary {
	private boolean[][] graph;
	private int n, m;
	private int[] match;
	private boolean[] used;

	public int[] hungaryDFS(boolean[][] g, int v1, int v2) {
		graph = g;
		n = v1;
		m = v2;
		match = new int[m];
		used = new boolean[m];
		for (int j = 0; j < m; j++)
			match[j] = -1;
		for (int i = 0; i < n; i++) {
			Arrays.fill(used, false);
			dfs(i);
		}
		return match;
	}

	private boolean dfs(int u) {
		for (int v = 0; v < m; v++)
			if (graph[u][v] && !used[v]) {
				used[v] = true;
				if (match[v] == -1 || dfs(match[v])) {
					match[v] = u;
					return true;
				}
			}
		return false;
	}

	public int hungaryBFS(boolean vc[][], int nv1, int nv2) {
		int i, j, x = 0, n;
		int q[] = new int[nv2], prev[] = new int[nv2], qs, qe;
		int vm1[] = new int[nv1], vm2[] = new int[nv2];
		n = 0;
		for (i = 0; i < nv1; i++)
			vm1[i] = -1;
		for (i = 0; i < nv2; i++)
			vm2[i] = -1;
		for (i = 0; i < nv1; i++) {
			for (j = 0; j < nv2; j++)
				prev[j] = -2;
			qs = qe = 0;
			for (j = 0; j < nv2; j++)
				if (vc[i][j]) {
					prev[j] = -1;
					q[qe++] = j;
				}
			while (qs < qe) {
				x = q[qs];
				if (vm2[x] == -1)
					break;
				qs++;
				for (j = 0; j < nv2; j++)
					if (prev[j] == -2 && vc[vm2[x]][j]) {
						prev[j] = x;
						q[qe++] = j;
					}
			}
			if (qs == qe)
				continue;
			while (prev[x] > -1) {
				vm1[vm2[prev[x]]] = x;
				vm2[x] = vm2[prev[x]];
				x = prev[x];
			}
			vm2[x] = i;
			vm1[i] = x;
			n++;
		}
		return n;
	}

}
